The invention relates to a method for processing network messages.
Modern utility or agricultural vehicles typically include a network of electronic control units (ECUs), such as an engine controller ECU, a transmission controller ECU, a dashboard instrumentation ECU, etc. The network may circumnavigate the vehicle to allow the various ECU""s to be located in proximity to the subsystem with which they are associated. A multitude of data messages are routinely broadcast on the network, of which each individual message may have relevance to only a few of the ECUs. For example, the engine controller ECU may provide engine speed information to the display ECU, but an ECU operating the vehicle lighting system will have no need for the engine speed information. Each ECU typically includes a chip set which includes a microprocessor (CPU) and CAN (Controller Area Network) networking hardware.
There exists applicable network protocol standards (SAE-J1939 and ISO-11783) which govern the communication of messages in such a network. Under the J1939 standard, messages include message identifiers. Message identifiers are the concatenation of several fields, including: (i) Priorityxe2x80x943 bits; (ii) Parameter Group Number (PGN)xe2x80x9416 bits; (iii) Destination Address (DA)xe2x80x948 bits; (iv) Source Address (SA)xe2x80x948 bits; and (v) Otherxe2x80x942 bits. So, these fields combine into a 29 bit message identifier.
The Priority field enables high priority messages to have preferred network access over lower priority. The PGN field is used to identify groups of parameters for more efficient network transport. An example is the grouping of engine speed and engine torque into one network message. Another group may have turn signal switches and other xe2x80x9ccourtesyxe2x80x9d type signals. Each group is assigned a number. Also, there are some values of PGN where the purpose is to allow direct communication from one ECU to another. In this case, part of the PGN is the destination address. The Destination Address field (DA) contains the unique address number assigned to every ECU on the network. Since every ECU has a unique number, one ECU can communicate directly to another ECU using a particular range of the PGN""s that are assigned to this purpose. The Source Address field (SA) is used for the unique number which is assigned to every ECU, so that the originating ECU of every message on the network can be identified. The xe2x80x9cOtherxe2x80x9d fields are reserved for future use.
In many instances, a message under the J1939 protocol will have pre-defined PGN""s (Parameter Group Numbers) corresponding to common parameters like engine speed, oil pressure, turn signal switches, etc. Many new ECU""s have parameters which are not pre-defined. J1939 also allows for xe2x80x9cproprietary messagingxe2x80x9d, wherein, for certain values of the PGN, the specifics of what data is carried in that PGN is left to the developers and will not appear in the J1939 standard. When new systems are created, it is common to prototype the system using these proprietary messages. If there is a need to put new parameters on the network, for example, xe2x80x9cradio antenna heightxe2x80x9d, a corresponding pre-defined PGN would not be found in the current J1939 database. So the system would be prototyped by using the proprietary messages to communicate the parameter xe2x80x9cradio antenna heightxe2x80x9d. Eventually, a PGN may be defined for such a parameter, but this involves a long lead time of many months to over a year.
In order to support these protocols, an extensive set of network messages must be supported. Each message that is received by an ECU microprocessor must have its message identifier examined to determine if this message is relevant to that particular ECU. For ECUs dealing with a small set of messages, the commonly available CAN networking hardware has built-in filtering which can perform this test, thereby automatically accepting messages of interest and rejecting other messages, without intervention of the ECU microprocessor. However, a typical ECU on such a network must process a much larger set of messages than the built-in hardware filters can manage, and therefore the acceptance and rejection of messages must be done in system software.
On a complex new system, there may be tens or even hundreds of new parameters. In such a system, these parameters are located in the xe2x80x9cproprietary messagexe2x80x9d PGN""s. But this group of PGN""s may not have the capacity for all of the new parameters. Therefore, it is a relatively common practice to use one data byte in the proprietary message to further describe the purpose of the specific message. Using one data byte provides 8 bits and therefore 256 additional unique combinations which allow association of particular parameters with corresponding PGNs.
When the message acceptance and rejection function is performed by system software, the CPU load is greatly increased, potentially to the extent that lower priority non-network related activity is at risk of not being performed in a timely manner. In order to overcome this problem, much more powerful CPU""s or other additional electronic hardware may be required. Either of these requirements would increase the system cost significantly.
Message identifiers are 29 bits long, and for some instances of message identifiers, examination of one or more of the data bytes may be required in order to determine relevancy of the message to a given ECU. Using conventional lookup table methods are not practical since the table may require more than 229th entries and if one of, the data bytes is further required to determine the relevancy of a given message, then 237th entries would be required. Also, message identifiers that are relevant to a particular ECU do not map into an addressing space with enough repetition such that an efficient mathematical formula could be used.
It is believed that typical current production networks implement a two step process, detecting and offloading messages as a high priority process and then processing messages as a low priority process. This process is time consuming to perform when many messages in the system have no relevance to a particular ECU or node. For example, an interrupt service routine (ISR) responding to a new message queues the message for later examination. If this message is not relevant, then this processing time is wasted, and conventional methods of determining message relevance require too much time in the ISR. Another example of wasted processing time is a lower priority process which periodically removes messages from the queue and compares them against the list of desired messages whether the messages are relevant or not.
In detail, the typical procedure for processing a CAN network message is as follows:
A network message arrives in the CAN subsystem of the ECU. This alerts the CPU via an interrupt. Normal processing is suspended and the ISR takes over to extract the message from the CAN subsystem, and move the message into a queue for later processing. This software is often very tightly designed to minimize the impact on other activities in the system and it is not obvious how to filter the messages in this ISR without adding extensive resources to the system. The CPU returns control to the previously active process. At a more convenient point in time, the CPU examines the queue for any messages that may be present. If one or more messages are present, they are individually examined to determine their relevance to this ECU in the network. This examination is typically done by comparing the unique identifier for this message against a list of known identifiers representing relevant messages. If the new message matches a message of interest, then the message is processed by this system. If the new message does not match, after having exhaustively compared the message identifier against all known identifiers of interest, then this message is rejected. The process repeats until some limit is reached. This limit may be an empty queue, some period of time, or some number of messages. The CPU performs other duties, and at some point in time in the future repeats this process.
With such a typical system, the ISR does a fixed amount of work requiring approximately 60 microseconds of CPU time. The message processor, scans the list of valued messages, requiring approximately 100 microseconds of CPU time to exhaustively search the list. Due to the large range of values for the message identifiers, there are not readily identifiable optimizations that can speed up the search, so it is typically a linear search. As the length of the list is increased, the time to scan the list is increased proportionally. If a message is found in the list, the message is then decoded. A typical ECU may find less than 20% of the messages to be relevant to it. For each message with no relevance, the CPU expends approximately 160 microseconds.
It would be desirable to provide a faster method for processing and determining relevance of network messages which is usable with less expensive CPU""s, which rejects messages with no relevance, and which can function during conditions of heavy network message loading.
Accordingly, an object of this invention is to provide a method for processing and determining relevance of network messages which is usable with less expensive CPU""s.
A further object of the invention is to provide such a method for processing and determining relevance of network messages which rejects messages with no relevance.
Another object of the invention is to provide a method for processing and determining relevance of network messages which can function during conditions of heavy network message loading.
These and other objects are achieved by the present invention, which performs a rapid mathematical hashing of the unique message identifier (which is up to 29 bits in length) of messages communicated over a network. This hashing function returns a small hash value, which is compared to index values in a relatively small lookup table which contains a relevance value for each index value. The table returns a 1 (or non-zero) for index values corresponding to relevant messages and a 0 for irrelevant messages. Relevant messages are accepted and queued into a RAM buffer. Irrelevant messages are rejected. This implementation is efficient and fast enough to be performed as part of an interrupt service routine ISR. Careful selection of the hashing function and table size produces a system that does not require additional filtering hardware. If the message is not relevant, then it is not queued and the ISR is complete, saving significant time in the ISR itself. Only those messages that pass through the above ISR xe2x80x9cfilteringxe2x80x9d are stored in a queue and eventually compared against a list of desired messages. If the message was rejected by the ISR, then no time is consumed for that message in this second stage of the process. When compared to the typical linear or binary search algorithm which could be used in the second stage of operation, this method saves a significant amount of CPU processing time for other processing needs.